# 第2节城市地图——图的深度优先遍历
book = [0 for i in range(0, 101)]
e = [[0 for i in range(0, 11)] for j in range(0, 11)]
_min = 999
n = 5
que = [0 for i in range(0, 101)]  # 队列记录路线


def dfs(cur, dis):
    global _min
    global head
    global tail
    # print('%d' % cur, end=' ')
    # 注释掉这个会打印所有路径
    # if dis > _min:
    #     return  # 距离大于最小距离退出
    if cur == n:
        # 输出路线
        j = 1
        while j < tail:
            print(que[j], end='->')
            j += 1
        print('路径长度%d' % dis)
        # 更新最小值
        if dis < _min:
            _min = dis
        return

    i = 1
    while i <= n:
        # 判断当前城市cur到i是否有路，并判断城市i是否在已经走过的路径中
        if e[cur][i] != -1 and book[i] == 0:
            que[tail] = i
            tail += 1
            book[i] = 1
            dfs(i, dis + e[cur][i])
            book[i] = 0  # 注意这里：之前一步探索完成，取消对城市的标记
            tail -= 1
        i += 1


if __name__ == '__main__':
    print('start')
    n = 5  # 变量n存储顶点的总个数
    m = 8  # 8条路
    # 初始化二维数组
    for i, v in enumerate(range(0, n + 1)):
        for j, v2 in enumerate(range(0, n + 1)):
            if i == j:
                e[i][j] = 0
            else:
                e[i][j] = -1  # 设9是正无穷

    # 读入城市之间的道路
    bian = [[0, 0, 0], [1, 2, 2], [1, 5, 10], [2, 3, 3], [2, 5, 7], [3, 1, 4], [3, 4, 4], [4, 5, 5], [5, 3, 3]]
    for i, v in enumerate(bian):
        if i > 0:
            a = bian[i][0]
            b = bian[i][1]
            e[a][b] = bian[i][2]
            # e[b][a] = bian[i][2] #改成无向图，最终结果是7
        # e[b][a] = 1  # 无向图，所以都要设为1
    # 输出图
    for i, v in enumerate(e):
        if 0 < i <= n:
            for j, v2 in enumerate(v):
                if 0 < j <= n:
                    print(v2, end=' ')
            print()
    print()
    # 从1号出发
    book[1] = 1  # 标记1号顶点已经被访问
    head = 1
    tail = 1
    que[tail] = 1
    tail += 1
    dfs(1, 0)  # 从1好顶点开始遍历
    print('最短路径%d' % _min)
